package com.cjm.algorithm.leetcode;

/**
 * 给定N个无限容量且初始均空的水缸， 每个水缸配有一个水桶来打水， 第i个水缸配备的水桶，
 * 容量记作bucket[i]， 有以下两种操作：
 * 升级水桶：选择任意一个水桶， 使其容量增加为bucket[i]+1
 * 蓄水：将全部水桶接满水， 倒入各自对应的水缸
 * <p>
 * 每个水缸对应最低蓄水量记作vat[i]， 返回小扣至少需要多少次操作可以完成所有水缸蓄水要求。
 * <p>
 * 注意：实际蓄水量【达到或超过】最低蓄水量， 即完成蓄水要求。
 */
public class StoreWaterLCP33 {
    public int storeWater(int[] bucket, int[] vat) {
        // 设置最大倒水次数
        int maxPull = 0;
        for (int i = 0; i < bucket.length; i++) {
            if (bucket[i] == 0 && vat[i] != 0) {
                // 如果桶为0 缸不为0 先升级桶为1， 再倒水
                maxPull = Math.max(maxPull, vat[i] + 1);
            } else {
                maxPull = (int) Math.max(maxPull, Math.ceil((double) vat[i] / (double) bucket[i]));
            }
        }
        if (maxPull == 0) {
            return 0;
        }
        // minNum存储最少， 倒水+升级 次数和
        int minNum = maxPull;
        for (int i = 0; i <= maxPull; i++) {
            // i为需要倒水的次数
            // fix = 升级次数
            int fix = 0;
            for (int j = 0; j < bucket.length; j++) {
                // Math.ceil(vat[j]/i) - bucket[j] i次装满需要桶的容量 - 先用桶的容量 = 升级次数
                fix += (vat[j] - i * bucket[j]) > 0 ? ((int)Math.ceil((double) vat[j] / (double) i) - bucket[j]):0;
            }
            minNum = Math.min(minNum, fix + i);
        }

        return minNum;
    }
}